﻿/**
 * N个点的无向图，每个点提供单车Si，
 * Si经过每条边需要 Si * Wi 的时间，
 * 问从1到N的最短时间
 * N在1000，使用平方算法即可
 * 令 Dij 为使用单车j到达点i所用的最短时间
 * 采用类似Dijkstra的刷表法
 * Dij 对 Dvj 和 Dvv 可能有贡献，其中v是i的邻点
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

using llt = long long;

struct _t{
    int node;
    int bike;
    llt d;
    _t() = default;
    _t(int a, int b, llt c):node(a),bike(b),d(c){}
    bool operator < (const _t & r) const {
        if(d != r.d) return d > r.d;
        if(node != r.node) return node > r.node;
        return bike > r.bike;
    }
};

int N, M;
vector<vector<pair<int, llt>>> G;
vector<vector<llt>> D;
vector<llt> S;

__gnu_pbds::priority_queue<_t> Q;

llt proc(){
    D.assign(N + 1, vector<llt>(N + 1, -1));

    Q.clear();
    Q.push({1, 1, 0});
    vector<vector<int>> flag(N + 1, vector<int>(N + 1, 0));

    while(1){
        while(not Q.empty() and flag[Q.top().node][Q.top().bike]) Q.pop();
        if(Q.empty()) break;

        auto h = Q.top(); Q.pop();
        flag[h.node][h.bike] = 1;

        for(const auto & p : G[h.node]){
            int v = p.first;
            llt w = p.second;
            llt tmp = w * S[h.bike] + h.d;
            if(-1 == D[v][h.bike] or tmp < D[v][h.bike]){
                Q.push({v, h.bike, D[v][h.bike] = tmp});
            }
            if(-1 == D[v][v] or tmp < D[v][v]){
                Q.push({v, v, D[v][v] = tmp});
            }
        }
    }

    llt ans = -1;
    const auto & d = D[N];
    for(int i=1;i<=N;++i){
        if(-1 == ans or d[i] < ans) ans = d[i];
    }
    return ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    int nofkase = 1;
    const array<string, 3> t {"ABC", "CAB", "BCA"};
    cin >> nofkase;
    while(nofkase--){
        cin >> N >> M;
        G.assign(N + 1, {});
        S.assign(N + 1, {});
        for(int a,b,w,i=0;i<M;++i){
            cin >> a >> b >> w;
            G[a].emplace_back(b, w);
            G[b].emplace_back(a, w);
        }
        for(int i=1;i<=N;++i) cin >> S[i];
        cout << proc() << "\n";
    }
    return 0;
}